package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC542 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 已经无力吐槽了，BFS还需要逆向扩散
     * 哎，奇技淫巧真的是多
     * 可以借鉴思想，多多学习
     * @return:
     */
    class Solution {
        public int[][] updateMatrix(int[][] matrix) {
            // 首先将所有的 0 都入队，并且将 1 的位置设置成 -1，表示该位置是 未被访问过的 1
            Queue<int[]> queue = new LinkedList<>();
            int m = matrix.length, n = matrix[0].length;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == 0) {
                        queue.offer(new int[]{i, j});
                    } else {
                        matrix[i][j] = -1;
                    }
                }
            }

            int[] dx = new int[]{-1, 1, 0, 0};
            int[] dy = new int[]{0, 0, -1, 1};
            while (!queue.isEmpty()) {
                int[] point = queue.poll();
                int x = point[0], y = point[1];
                for (int i = 0; i < 4; i++) {
                    int newX = x + dx[i];
                    int newY = y + dy[i];
                    // 如果四邻域的点是 -1，表示这个点是未被访问过的 1
                    // 所以这个点到 0 的距离就可以更新成 matrix[x][y] + 1。
                    if (newX >= 0 && newX < m && newY >= 0 && newY < n
                            && matrix[newX][newY] == -1) {
                        matrix[newX][newY] = matrix[x][y] + 1;
                        queue.offer(new int[]{newX, newY});
                    }
                }
            }

            return matrix;
        }
    }


    /**
     * DFS是不可能找出最短路径的
     */
    class Solution_DFS_FAIL {
        private int[][] directions = {
                {0, 1},
                {0, -1},
                {1, 0},
                {-1, 0}};

        public int[][] updateMatrix(int[][] matrix) {
            int[][] distance = new int[matrix.length][matrix[0].length];
            boolean[][] visited = new boolean[matrix.length][matrix[0].length];
            for (int i = 0; i < matrix.length; i++)
                for (int j = 0; j < matrix[0].length; j++)
                    distance[i][j] = Integer.MAX_VALUE;

            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (matrix[i][j] == 0) distance[i][j] = 0;
                    else distance[i][j] = DFSSearchLength(matrix, distance, visited, i, j);
                }
            }

            return distance;
        }

        public int DFSSearchLength(int[][] matrix, int[][] distance, boolean[][] visited, int x, int y) {
            if (distance[x][y] < Integer.MAX_VALUE) return distance[x][y];
            if (matrix[x][y] == 0) return 0;

            visited[x][y] = true;
            int surroundX, surroundY, curDist = Integer.MAX_VALUE;
            for (int[] d : directions) {
                surroundX = x + d[0];
                surroundY = y + d[1];
                if (surroundX < 0 || surroundX >= matrix.length || surroundY < 0 ||
                        surroundY >= matrix[0].length || visited[surroundX][surroundY])
                    continue;
                int surroundDist = DFSSearchLength(matrix, distance, visited, surroundX, surroundY) + 1;
                curDist = Math.min(curDist, surroundDist);
            }

            visited[x][y] = false;
            distance[x][y] = curDist;
            return curDist;
        }
    }

    class Solution_Time_Exceed {
        private int[][] directions = {
                {0, 1},
                {0, -1},
                {1, 0},
                {-1, 0}};

        public int[][] updateMatrix(int[][] matrix) {
            int[][] distance = new int[matrix.length][matrix[0].length];
            for (int i = 0; i < matrix.length; i++)
                for (int j = 0; j < matrix[0].length; j++)
                    distance[i][j] = Integer.MAX_VALUE;

            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (matrix[i][j] == 0) distance[i][j] = 0;
                    else distance[i][j] = BFSSearchLength(matrix, distance, i, j);
                }
            }

            return distance;
        }

        public int BFSSearchLength(int[][] matrix, int[][] distance, int x, int y) {
            boolean[][] visited = new boolean[matrix.length][matrix[0].length];
            int layerLength = 0;
            Deque<int[]> queue = new LinkedList<>();
            queue.offerLast(new int[]{x, y});
            while (!queue.isEmpty()) {
                int size = queue.size();
                ++layerLength;
                for (int i = 0; i < size; i++) {
                    int[] cur = queue.pollFirst();
                    visited[cur[0]][cur[1]] = true;
                    int surroundX, surroundY;
                    for (int[] d : directions) {
                        surroundX = cur[0] + d[0];
                        surroundY = cur[1] + d[1];
                        if (surroundX < 0 || surroundX >= matrix.length || surroundY < 0 ||
                                surroundY >= matrix[0].length || visited[surroundX][surroundY])
                            continue;
                        if (matrix[surroundX][surroundY] == 0) return layerLength;
                        queue.offerLast(new int[]{surroundX, surroundY});
                    }
                }
            }

            return Integer.MAX_VALUE;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[][] arr = InputUtil.toDoubleIntegerArray("[[1,0,1,1,0,0,1,0,0,1],[0,1,1,0,1,0,1,0,1,1],[0,0,1,0,1,0,0,1,0,0],[1,0,1,0,1,1,1,1,1,1],[0,1,0,1,1,0,0,0,0,1],[0,0,1,0,1,1,1,0,1,0],[0,1,0,1,0,1,0,0,1,1],[1,0,0,0,1,1,1,1,0,1],[1,1,1,1,1,1,1,0,1,0],[1,1,1,1,0,1,0,0,1,1]]");
        System.out.println(solution.updateMatrix(arr));
    }

    public static void main(String[] args) throws Exception {
        LC542 an = new LC542();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
